package Algorithm.string;

import java.util.HashMap;
import java.util.Map;

/**
 * @Desc:最小覆盖子串
 * 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
 *
 * 示例：
 *
 * 输入: S = "ADOBECODEBANC", T = "ABC"
 * 输出: "BANC"
 * 说明：
 *
 * 如果 S 中不存这样的子串，则返回空字符串 ""。
 * 如果 S 中存在这样的子串，我们保证它是唯一的答案。
 *
 * @author: cww
 * @DateTime: 2020-05-14 0:43
 */

public class MinWindow {

    public static void main(String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";
        System.out.println(minWindow(s,t));
    }

    public static String minWindow(String s, String t){
        if (s.length()==0||t.length()==0) return "";
        Map<Character, Integer> dictT = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            int count = dictT.getOrDefault(t.charAt(i), 0);
            dictT.put(t.charAt(i), count+1);
        }
        // 目标窗口大小
        int required = dictT.size();
        int l = 0,r=0;
        // 当前窗口中存在目标字符的统计
        int formed = 0;
        // 当前窗口元素个数
        Map<Character, Integer> windowCounts = new HashMap<>();
        // (window length, left, right)
        int[] ans = {-1,0,0};
        while (r<s.length()){
            // 将 s[r] 存入 windowCounts，并更新统计值
            char c = s.charAt(r);
            int count = windowCounts.getOrDefault(c, 0);
            windowCounts.put(c, count+1);
            // 如果当前添加的字符存在与目标字符中且个数相同，则 formed 加一
            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()){
                formed++;
            }
            // 尝试收缩窗口，直到当前统计 formed 不等于 目标窗口 required
            while (l<=r && formed == required){
                c = s.charAt(l);
                // 保存当前最小的窗口,r-l+1是当前窗口大小，如果当前窗口比上一次窗口小，则更新 ans 的属性
                if (ans[0] == -1||r-l+1<ans[0]){
                    ans[0] = r -l +1;
                    ans[1] = l;
                    ans[2] = r;
                }
                // 窗口要右移，所以将最左边指针对应的字符移除当前 windowCounts 窗口
                windowCounts.put(c,windowCounts.get(c)-1);
                // 当上一步移除后需要更新 formed；< 意思是如果当前窗口左移除后如果当前字符个数小于目标窗口，那么统计值 formed要减，如果还是大于等于则不用
                if(dictT.containsKey(c)&&windowCounts.get(c).intValue()< dictT.get(c).intValue()){
                    formed--;
                }
                l++;
            }
            r++;
        }
        return ans[0]==-1?"":s.substring(ans[1],ans[2]+1);
    }

    public static String minWindow1(String s, String t){
        // 惯例判空
        if (s.length()==0||t.length()==0) return "";
        // 将目标 t 维护到t窗口中
        Map<Character, Integer> tMap = new HashMap<>();
        for(int i=0;i<t.length();i++){
            int count = tMap.getOrDefault(t.charAt(i),0);
            tMap.put(t.charAt(i), count);
        }
        // 初始化 目标窗口、指针、结果、当前匹配个数
        // 目标窗口字符数
        int targetCount = tMap.size();
        Map<Character, Integer> windowsMap = new HashMap<>();
        int matchCount = 0,l=0,r=0;
        int[] ans = {-1,0,0};

        // 循环判断有指针是否到达右边
        while(r<s.length()){
            // 将当前字符放入当前目标c窗口,相当于窗口右移
            char c = s.charAt(r);
            int count = windowsMap.getOrDefault(c, 0);
            windowsMap.put(c, count +1);
            // 当前字符是否在目标 t 中，如果存在则将统计+1
            if(tMap.containsKey(c)&&windowsMap.get(c).intValue()==tMap.get(c).intValue()){
                matchCount++;
            }

            // 当前统计是否 == t的size,如果相等就可以开始右移l指针，
            while(l<=r && matchCount == targetCount){
                c = s.charAt(l);
                if(ans[0] == -1||l-r+1<ans[0]){
                    ans[0]=l-r+1;
                    ans[1]=l;
                    ans[2]=r;
                }
                windowsMap.put(c,windowsMap.get(c)-1);
                if(tMap.containsKey(c)&&windowsMap.get(c).intValue()<tMap.get(c).intValue()){
                    matchCount--;
                }
                l++;
            }
            r++;
        }
        return ans[0]==-1?"": s.substring(ans[1],ans[2]+1);

    }
}
